#include "common_headers.h"

/*--- Initialize BST root ---*/
void initialize_BST(){
bst_root=NULL;
}

struct BST_Node * mallocNode()//allocating memory for the nodes
{
        struct BST_Node * temp;
        temp= (struct BST_Node*)malloc(sizeof(struct BST_Node));
        temp->left=NULL;
        temp->right=NULL;
	temp->parent=NULL;
        return temp;
}

int validatePath(struct BST_Node  *newNode,struct BST_Node  *root)
{
	int flag;
	
 	/*--- If the node is already existing, don't insert ---*/
	if(strcasecmp(newNode->data->locationpath,root->data->locationpath)==0)
	{
		flag=1;
	}
		
	if(strcasecmp(newNode->data->locationpath,root->data->locationpath)>0)
	{
		/*--- new_node < temp   =>   go to left child ---*/
		flag=2;
	}
	if(strcasecmp(newNode->data->locationpath,root->data->locationpath)<0)
	{
		/*--- new_node > temp   =>   go to right child ---*/
		flag=3;
	}
return flag;
}

void BSTInsert(struct FileDescriptor* fd )
{
// int isValid;

        struct BST_Node  *bstFirst,*root;
        struct BST_Node *newNode=mallocNode();
	int valid,testval;
        if(newNode==NULL)
        {
                printf("INSUFFICIENT");//system out of memory
                exit(0);
        }
        
	if(bst_root==NULL)
        {
		newNode->data=fd;
                bst_root=newNode;
		
        }        
        else // bst will be either right or left skewed 
        {
		root=bst_root;
		newNode->data=fd;
               	while(root)
		{	
			valid=validatePath(newNode,root);
                      //printf("%s\n",fdesc->fullPath );
			if(valid==1)
                	{
                        	printf("File already exists\n");
                        	return;
                	}
                        else if(valid==3)
                        {     
                                bstFirst=root;         // prev node
                                root=root->left;
				testval=0;
                        }
                        else if(valid==2)
                        {
				bstFirst=root;         // prev node
                                root=root->right;
				testval=1;
                        }
                        
                               
			//return root;
          	}
                
		if(testval==0)
		{
			newNode->parent=bstFirst;
			bstFirst->left=newNode;
		}
		else if(testval==1){

			newNode->parent=bstFirst;
			bstFirst->right=newNode;
		}
          
	}

}



/*--- Transplant u with v ---*/
 void transplant(struct BST_Node *root,struct BST_Node* u,struct BST_Node* v)
{
        /*--- If u's parent is NULL  =>  v will be the root ---*/
        if(u->parent==NULL)// memory leak not freeing memory
	{
		bst_root=v;
	}
                
        /*--- If u is u's parent's left child  => now u's parent's left will be v (v is taking u's position) ---*/
        else if(u==u->parent->left)
	{	
		u->parent->left=v;
	}
                
        else
	{
                u->parent->right=v;
	}
        /*--- If u is u's parent's right child  => now u's parent's right will be v (v is taking u's position) ---*/


        if(v!=NULL)
	{
		v->parent=u->parent;
	}
        /*--- Now, whatever was u's parent, that becomes v's parent ---*/
                
}

int flagReturn(struct BST_Node *bstNode)
{
	int flag;

	if(bstNode==NULL)
	{
		flag=0;
	}
	else if(bstNode->left==NULL)
	{
		flag=1;
	}
	else if(bstNode->right==NULL)
	{
		flag=2;
	}
	return flag;
}

void delete_bstnode(struct BST_Node *root, char path[300])
{

        struct BST_Node *y,*z,*k;
	int retval;
        /*--- search the node whose filedescriptor->locationpath is the 'path'---*/
        z = search(root,path);
        /*--- If the searched node is null, that means, there is no node to delete---*/
	retval=flagReturn(z);
        if(retval==0)
        {
                return;
        }
        /*--- If z's left is null, then transplant z with z's right---*/
        if(retval==1)
	{
                transplant(root,z,z->right);
	}

        /*--- If z's right is null, then transplant z with z's left---*/
        else if(retval==2)
	{
                transplant(root,z,z->left);
	}

        else
        {
                /*--- If z has a right child, y = z's successor in z's right subtree---*/
		k=z->right;
		while(y->left!=NULL)
        	{
                		y=y->left;
       		}
                /*---If y is not the direct right child of z, make y's right to be in y's position and make z's right subtree as y's right subtree so that z can be deleted---*/
                if(y->parent!=z)
                {
                        transplant(root,y,y->right);
                        y->right=z->right;
                        y->right->parent=y;
                }
                /*---Transplant z with y and make the left subtree of z as the left subtree of its successor, y so that z can be deleted---*/
                transplant(root,z,y);
                y->left=z->left;
                y->left->parent=y;
        }
}


int validateSearch(struct BST_Node* bstfirst,char* search_val)
{
	int flag;

	if(strcasecmp(bstfirst->data->locationpath,search_val)==0)
	{
		//bstfirst is the first node...compare path of root and path of node to be searched ignoring case
		//\nFile successfully found;
		flag=1;
	}
	if(strcasecmp(bstfirst->data->locationpath,search_val)>0)
	{
		//go to right of bstfirst(first node) ignoring case
		flag=2;
	}
	if(strcasecmp(bstfirst->data->locationpath,search_val)<0)
	{
		//go to right of bstfirst(first node)
		flag=3;
	}

return flag;

}


struct BST_Node* search(struct BST_Node* node,char* search_val)
{   
	struct BST_Node* bstfirst;
        bstfirst=node;
	int retval;
        if(bstfirst==NULL)
        {
                //no bstroot to search
                return NULL;
        }
        else
        {
                while(bstfirst!=NULL)
                {
                        retval=validateSearch(bstfirst,search_val);

                        if(retval==1)
                        {
                                return bstfirst;
                        }
                        else if(retval==2)
                        {
                                bstfirst=bstfirst->right;
                        }
                        else if(retval==3)
                        {
                                bstfirst=bstfirst->left;
                        }
                }
		
		
        }
       
      //  return;

}

void displayBST(struct BST_Node *root)
{
        if(root)
        {
                displayBST(root->left);
                printf("%s\n",root->data->locationpath);
                displayBST(root->right);
        }
else
return;
}


